package data_structur.Recursion;

/**
 * 递归
 * 解决迷宫问题
 */
public class MazeDemo {

    public static void main(String[] args) {
        // 新建二维数组模拟迷宫
        int[][] map = new int[8][7];

        // 将地图周围设置为墙，强用1表示
        // 上下变墙
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        // 左右变墙
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        // 设置挡板
        map[3][1] = 1;
        map[3][2] = 1;

        // 打印地图
        System.out.println("Old map:");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

        // 走一把
        System.out.println("\n" + setWay(map, 1, 1) + "\n");


        // 输出新地图
        System.out.println("New map:");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 使用数组模拟迷宫，采用 下-右-上-左 的策略行动，走不通就回溯
     * 地图中0代表没走过，1代表障碍，2代表通路，3代表走过但走不通
     * @param map 地图
     * @param i x坐标
     * @param j y坐标
     * @return 能否找到通路
     */
    public static boolean setWay(int[][] map, int i, int j){
        // 已经找到通路就返回
        if (map[6][5] == 2){
            return true;
        }
        // 没找到的话就继续走
        //第一种情况，这个路没走过则采用 下-右-上-左 策略
        if (map[i][j] == 0){
            map[i][j] = 2; // 假定这个路可以走通
            if (setWay(map, i+1, j)){ // 向下走
                return true;
            } else if (setWay(map, i, j+1)){ // 向右走
                return true;
            } else if (setWay(map, i-1, j)){ // 向上走
                return true;
            } else if (setWay(map, i, j-1)){ // 向左走
                return true;
            } else { // 都走不通说明是死路
                map[i][j] = 3;
                return false;
            }
        } else { // 如果不为0，则为1或3，直接返回false
            return false;
        }
    }

    // 行走的路径长短其实与设定的行动策略有关，一旦更改，路径将发生变化，右上左下为例
    public static boolean setWay2(int[][] map, int i, int j){
        if (map[6][5] == 2){
            return true;
        }

        if (map[i][j] == 0){
            map[i][j] = 2;
            if (setWay2(map, i, j+1)){
                return true;
            } else if (setWay2(map, i+1, j)){
                return true;
            } else if (setWay2(map, i, j-1)){
                return true;
            } else if (setWay2(map, i-1, j)){
                return true;
            } else {
                map[i][j] = 3;
                return false;
            }
        } else {
            return false;
        }
    }

}
